package com.south.base.test.arithmetic.dynamic.programming;

import org.junit.Assert;
import org.junit.Test;

import java.util.Arrays;

/**
 * @author Administrator
 * @date 2019/8/30 10:57
 */
public class CoinsChange {
    /**
     * 给出不同面额的硬币以及一个总金额. 写一个方法来计算给出的总金额可以换取的最少的硬币数量.
     * 如果已有硬币的任意组合均无法与总金额面额相等, 那么返回 -1.
     */
    @Test
    public void coinChange() {
        Assert.assertEquals(coinChange(new int[]{1, 2, 4}, 32000), 8000);
        Assert.assertEquals(coinChange(new int[]{1, 2, 5}, 11), 3);

        Assert.assertEquals(coinChange2(new int[]{1, 2, 4}, 32000), 8000);
        Assert.assertEquals(coinChange2(new int[]{1, 2, 5}, 11), 3);
    }

    public int coinChange(int[] coins, int amount) {
        int[] f = new int[amount + 1];
        f[0] = 0;
        int i, j;
        for (i = 1; i <= amount; i++) {
            f[i] = Integer.MAX_VALUE;
            for (j = 0; j < coins.length; j++) {
                if (i >= coins[j] && f[i - coins[j]] != Integer.MAX_VALUE) {
                    f[i] = Math.min(f[i - coins[j]] + 1, f[i]);
                }
            }
        }
        return f[amount] == Integer.MAX_VALUE ? -1 : f[amount];
    }

    public int coinChange2(int[] coins, int amount) {
        int[] f = new int[amount + 1];
        Arrays.sort(coins);
        coinChange2(f, coins, amount);
        return f[amount] == Integer.MAX_VALUE ? -1 : f[amount];
    }

    /**
     * FIXME 递归调用易栈溢出
     *
     * @param f
     * @param coins
     * @param i
     */
    private void coinChange2(int[] f, int[] coins, int i) {
        if (i == 0) {
            return;
        }
        f[i] = Integer.MAX_VALUE;
        for (int j = coins.length - 1; j >= 0; j--) {
            int coin = coins[j];
            if (i >= coin && f[i - coin] == 0) {
                coinChange2(f, coins, i - coin);
            }
            if (i >= coin && f[i - coin] != Integer.MAX_VALUE) {
                f[i] = Math.min(f[i - coin] + 1, f[i]);
            }
        }
    }

    private int res = Integer.MAX_VALUE;

    public int coinChange3(int[] coins, int amount) {
        Arrays.sort(coins);
        helper(coins, coins.length - 1, 0, amount);
        return res == Integer.MAX_VALUE ? -1 : res;
    }

    private void helper(int[] coins, int start, int cur, int amount) {
        if (start < 0) return;
        if (amount % coins[start] == 0) {
            res = Math.min(res, cur + amount / coins[start]);
            return;
        }
        for (int i = amount / coins[start]; i >= 0; i--) {
            // System.out.println("cur = " + cur + ", i = " + i + ", res = " + res);
            if (cur + i >= res - 1) break;
            helper(coins, start - 1, cur + i, amount - i * coins[start]);
        }
    }

    /**
     * 给定一个非负整数 num。对于 0 ≤ i ≤ num 范围中的每个数字 i ，计算其二进制数中的 1 的数目并将它们作为数组返回。
     */
    @Test
    public void countBits() {
        Assert.assertArrayEquals(new int[]{0, 1, 1}, countBits(2));
        Assert.assertArrayEquals(new int[]{0,1,1,2,1,2}, countBits(5));
        Assert.assertArrayEquals(new int[]{0, 1, 1}, countBits2(2));
        Assert.assertArrayEquals(new int[]{0,1,1,2,1,2}, countBits2(5));
    }

    public int[] countBits(int num) {
        int[] res = new int[num + 1];
        for (int i = 1; i <= num; i++) {
            int count = 0;
            for (int j = 0; j < 32; j++) {
                count += i >> j & 1;
            }
            res[i] = count;
        }
        return res;
    }

    public int[] countBits2(int num) {
        int[] res = new int[num + 1];
        int b = 1, i = 0;
        while (b <= num) {
            // generate [b, 2b) or [b, num) from [0, b)
            while (i < b && i + b <= num) {
                res[i + b] = res[i] + 1;
                ++i;
            }
            i = 0;   // reset i
            b <<= 1; // b = 2b
        }
        return res;
    }
}
